/*
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0 <= n <= 2×10^5，区间内 的值都满足 0 <= val <= 2×10^5
 
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
进阶：空间复杂度 O(val)，时间复杂度O(val)

输入1：
[[10,30],[20,60],[80,100],[150,180]]
返回值：
[[10,60],[80,100],[150,180]]

输入2：
[[0,10],[10,20]]
返回值：
[[0,20]]
*/


#include <stdlib.h>
#include <stdio.h>

 struct Interval {
 	int start;
 	int end;
 };

 /**
  *
  * @param intervals Interval类一维数组
  * @param intervalsLen int intervals数组长度
  * @return Interval类一维数组
  * @return int* returnSize 返回数组行数
  */
int cmp(const void *a, const void *b)
{
    /* 大于0 就交换 */
    return (((struct Interval *)a)->start - ((struct Interval *)b)->start);
}

struct Interval *merge(struct Interval *intervals, int intervalsLen, int *returnSize) {
    /*
    i : 下标
    k : 限制用辅助变量
    returnlen : 计算最终返回长度用的 过程临时变量
    */
    int i;
    int k = 1; /* 用来保证只取有效的区间；也可以说是用来找到需要删除的区间的位置 */
    int returnLen = 0;

    if (intervals == NULL || returnSize == NULL || intervalsLen < 0 || intervalsLen > 1000) {
        printf("input error!\n");
        return NULL;
    }

    returnLen = intervalsLen;
    /* 升序排序 */
    qsort(intervals, intervalsLen, sizeof(struct Interval), cmp);
    /* 合并重叠区间 */
    for (i = 1; i < intervalsLen; i++) {   // 除了滑窗，一般不考虑用while循环
        /* 第i个区间末端与前一个有效的区间的末端比较，比前一个小就合并 */
        if (intervals[i].end <= intervals[i - k].end) {                 // 第1种合并场景
            /* 合并一次返回长度就减1 */
            returnLen--;
            /* k用于保证每次只与前一个进行了合并操作的有效区间相比较 */
            k++;
            //
        } else if (intervals[i].start <= intervals[i - k].end) {        // 第2种合并场景
            /* 第i个与前一个有效区间有交集，则合并 */
            intervals[i - k].end = intervals[i].end;
            returnLen--;
            k++;
        } else {
            /* 1.没有重叠则相当于不变 */
            /* 2.发生了重叠，这里的操作则相当于把值左移。这里intervals总的成员数没有减少，所以返回一个长度来说明只有前returnSize个成员是有效的 */
            intervals[i - k + 1].start = intervals[i].start;
            intervals[i - k + 1].end = intervals[i].end;
        }
    }

    *returnSize = returnLen;
    return intervals;
}

int main(void)
{
    struct Interval intervals[4] = {
        {10, 30},
        {20, 60},
        {80, 100},
        {150, 180}
    };
    struct Interval *res = NULL;  // 应该使用malloc，不应该直接指向NULL
    int returnSize = 1;  // windows下VS2022给0则相当于给NULL，会出问题
    int intervalsLen = 4;  // 4个成员

    res = merge(intervals, intervalsLen, &returnSize);
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d, %d]", intervals[i].start, intervals[i].end);
        if (i < returnSize - 1) {
            printf(",");
        }
    }
    printf("]\n");

	return 0;
}
